/* -*- Mode: c; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil; -*- */
/*
  RefObject (http://code.google.com/p/refobject/)
  Copyright (C) 2010-2011 MIURA Shirow (sharow)
*/

#include "RefDictInternal.h"
#include "RefModuleInternal.h"
#include <RefObject/RefAllocator.h>
#include <RefObject/RefList.h>
#include <RefObject/RefString.h>
#include "RefAssert.h"


typedef struct {
    RefObject *mRefKeyString;
    RefObject *mRefValue;
    unsigned long mHash;
    RefObject *mRefAllocator;
} RefDictPrimitiveNode;

typedef struct {
    RefObject *mRefList;
    RefObject *mRefAllocator;
} RefDictListNode;

typedef struct {
    RefObject **mNodeTable;
    int mNodeTableSize;
    int mNumNode;
    RefObject *mRefAllocator;
} RefDict;


static RefTypeObject *gDictTypeObject = NULL;
static RefTypeObject *gDictPrimitiveNodeTypeObject = NULL;
static RefTypeObject *gDictListNodeTypeObject = NULL;


/* RefDictPrimitiveNode */

/* not use
static RefTypeObject **
RefDictPrimitiveNode_GetTypeObject(void)
{
    return &gDictPrimitiveNodeTypeObject;
}
*/

static int
RefDictPrimitiveNode_IsValid(RefObject *aRefObject)
{
    return (RefObject_GetTypeObject(aRefObject) == &gDictPrimitiveNodeTypeObject);
}

static void
RefDictPrimitiveNode_Destructor(RefObject *aRefObject)
{
    RefDictPrimitiveNode *node;
    RefObject *refallocator;
    node = RefObject_GetObject(aRefObject);
    refallocator = node->mRefAllocator;
    RefObject_DecRef(node->mRefKeyString);
    RefObject_DecRef(node->mRefValue);
    RefAllocator_Free(refallocator, aRefObject);
    RefObject_DecRef(refallocator);
}

static RefObject *
RefDictPrimitiveNode_Create(RefObject *aRefKeyString, RefObject *aRefValue,
                            unsigned long aHash, RefObject *aRefAllocator)
{
    RefObject *refobj;
    RefDictPrimitiveNode *node;
    refobj = RefAllocator_Alloc(aRefAllocator, RefObject_SizeOf() + sizeof(*node));
    node = RefObject_Construct(refobj, &gDictPrimitiveNodeTypeObject, RefDictPrimitiveNode_Destructor);
    node->mRefKeyString = aRefKeyString;
    RefObject_IncRef(aRefKeyString);
    node->mRefValue = aRefValue;
    RefObject_IncRef(aRefValue);
    node->mHash = aHash;
    node->mRefAllocator = aRefAllocator;
    RefObject_IncRef(aRefAllocator);
    return refobj;
}


/* RefDictListNode */

/* not use
static RefTypeObject **
RefDictListNode_GetTypeObject(void)
{
    return &gDictListNodeTypeObject;
}
*/

static int
RefDictListNode_IsValid(RefObject *aRefObject)
{
    return (RefObject_GetTypeObject(aRefObject) == &gDictListNodeTypeObject);
}

static void
RefDictListNode_Destructor(RefObject *aRefObject)
{
    RefDictListNode *node;
    RefObject *refallocator;
    node = RefObject_GetObject(aRefObject);
    refallocator = node->mRefAllocator;
    RefObject_DecRef(node->mRefList);
    RefAllocator_Free(refallocator, aRefObject);
    RefObject_DecRef(refallocator);
}

static RefObject *
RefDictListNode_CreateWithAllocator(RefObject *aRefAllocator)
{
    RefObject *refobj;
    RefDictListNode *node;
    refobj = RefAllocator_Alloc(aRefAllocator, RefObject_SizeOf() + sizeof(*node));
    node = RefObject_Construct(refobj, &gDictListNodeTypeObject, RefDictListNode_Destructor);
    node->mRefList = RefList_CreateWithAllocator(aRefAllocator);
    node->mRefAllocator = aRefAllocator;
    RefObject_IncRef(aRefAllocator);
    return refobj;
}

static int
RefDictListNode_Append(RefObject *aRefListNode, RefObject *aRefPrimitiveNode)
{
    RefDictListNode *node;
    node = RefObject_GetObject(aRefListNode);
    return RefList_Append(node->mRefList, aRefPrimitiveNode);
}

static int
RefDictListNode_GetSize(RefObject *aRefListNode)
{
    return RefList_GetSize(((RefDictListNode *)RefObject_GetObject(aRefListNode))->mRefList);
}

static RefObject *
RefDictListNode_GetItem(RefObject *aRefListNode,
                        unsigned long aHash,
                        unsigned char *aCString,
                        int aLength)
{
    RefDictListNode *node;
    int i;
    int size;
    node = RefObject_GetObject(aRefListNode);
    size = RefList_GetSize(node->mRefList);
    for (i = 0; i < size; i++) {
        RefDictPrimitiveNode *primitive_node;
        primitive_node = RefObject_GetObject(RefList_GetItem(node->mRefList, i));
        if (aHash == primitive_node->mHash &&
            RefString_CompareCStringWithLength(primitive_node->mRefKeyString, aCString, aLength) == 0) {
            return primitive_node->mRefValue;
        }
    }
    return NULL;
}

static RefObject *
RefDictListNode_TakeOutItem(RefObject *aRefListNode,
                            unsigned long aHash,
                            unsigned char *aCString,
                            int aLength)
{
    RefDictListNode *node;
    int i;
    int size;
    node = RefObject_GetObject(aRefListNode);
    size = RefList_GetSize(node->mRefList);
    for (i = 0; i < size; i++) {
        RefDictPrimitiveNode *primitive_node;
        primitive_node = RefObject_GetObject(RefList_GetItem(node->mRefList, i));
        if (aHash == primitive_node->mHash &&
            RefString_CompareCStringWithLength(primitive_node->mRefKeyString, aCString, aLength) == 0) {
            RefObject *refobject;
            refobject = primitive_node->mRefValue;
            RefObject_IncRef(refobject);
            RefList_DeleteItem(node->mRefList, i);
            return refobject;
        }
    }
    return NULL;
}

static RefObject *
RefDictListNode_GetItemByIndex(RefObject *aRefListNode, int aIndex)
{
    RefDictListNode *node;
    node = RefObject_GetObject(aRefListNode);
    return RefList_GetItem(node->mRefList, aIndex);
}


/* RefDict */

RefTypeObject **
RefDict_GetTypeObject(void)
{
    return &gDictTypeObject;
}

int
RefDict_IsValid(RefObject *aRefObject)
{
    return (RefObject_GetTypeObject(aRefObject) == &gDictTypeObject);
}

static void
RefDict_Destructor(RefObject *aRefObject)
{
    RefDict *dict;
    RefObject *refallocator;
    int i;
    dict = RefObject_GetObject(aRefObject);
    refallocator = dict->mRefAllocator;
    for (i = 0; i < dict->mNodeTableSize; i++) {
        if (dict->mNodeTable[i]) {
            RefObject_DecRef(dict->mNodeTable[i]);
        }
    }
    RefAllocator_Free(refallocator, dict->mNodeTable);
    RefAllocator_Free(refallocator, aRefObject);
    RefObject_DecRef(refallocator);
}

static int
RefDict_GetNextTableSize(int aPrevSize)
{
    if (aPrevSize == 0) {
        return 64;
    } else if (aPrevSize < 1024) {
        return aPrevSize * 2;
    } else {
        return (aPrevSize * 3) >> 1;
    }
}

/* from: http://en.wikipedia.org/wiki/Jenkins_hash_function */
static unsigned long
RefDict_HashWithLength(const unsigned char *aString, int aStringLength)
{
    unsigned long full_hash;
    const unsigned char *p;
    int i;
    full_hash = 0;
    for (p = aString, i = 0; i < aStringLength; p++, i++) {
        full_hash += *p;
        full_hash += (full_hash << 10);
        full_hash ^= (full_hash >> 6);
    }
    full_hash += (full_hash << 3);
    full_hash ^= (full_hash >> 11);
    full_hash += (full_hash << 15);
    return full_hash;
}

/* not use
static unsigned long
RefDict_HashWithoutLength(const unsigned char *aString)
{
    unsigned long full_hash;
    const unsigned char *p;
    full_hash = 0;
    for (p = aString; *p != '\0'; p++) {
        full_hash += *p;
        full_hash += (full_hash << 10);
        full_hash ^= (full_hash >> 6);
    }
    full_hash += (full_hash << 3);
    full_hash ^= (full_hash >> 11);
    full_hash += (full_hash << 15);
    return full_hash;
}
*/

RefObject *
RefDict_CreateWithAllocator(RefObject *aRefAllocator)
{
    RefObject *refobj;
    RefDict *dict;
    int table_size;
    int i;
    table_size = RefDict_GetNextTableSize(0);
    refobj = RefAllocator_Alloc(aRefAllocator, RefObject_SizeOf() + sizeof(*dict));
    dict = RefObject_Construct(refobj, &gDictTypeObject, RefDict_Destructor);
    dict->mNodeTable = RefAllocator_Alloc(aRefAllocator, sizeof(*dict->mNodeTable) * table_size);
    for (i = 0; i < table_size; i++) {
        dict->mNodeTable[i] = NULL;
    }
    dict->mNodeTableSize = table_size;
    dict->mNumNode = 0;
    dict->mRefAllocator = aRefAllocator;
    RefObject_IncRef(aRefAllocator);
    return refobj;
}

RefObject *
RefDict_Create(RefObject *aRefAllocator)
{
    return RefDict_CreateWithAllocator(RefModule_GetSingletonAllocator());
}

static int
RefDict_ResizeNodeTable(RefDict *aDict, int aNewSize)
{
    /* TODO */
    return 0;
}

int
RefDict_SetItem(RefObject *aRefDict, RefObject *aRefKeyString, RefObject *aRefValue)
{
    RefDict *dict;
    RefObject *primtive_node;
    unsigned char *key_cstring;
    int key_cstring_len;
    unsigned long full_hash;
    int index;
    dict = RefObject_GetObject(aRefDict);
    key_cstring = RefString_AsString(aRefKeyString);
    key_cstring_len = RefString_GetLength(aRefKeyString);
    full_hash = RefDict_HashWithLength(key_cstring, key_cstring_len);
    primtive_node = RefDictPrimitiveNode_Create(aRefKeyString, aRefValue,
                                                full_hash, dict->mRefAllocator);
    index = full_hash & (dict->mNodeTableSize - 1);
    if (dict->mNodeTable[index]) {
        if (RefDictPrimitiveNode_IsValid(dict->mNodeTable[index])) {
            RefObject *old_primtive_node;
            /*printf("RefDict_SetItem(): new ListNode\n");*/
            old_primtive_node = dict->mNodeTable[index];
            dict->mNodeTable[index] = RefDictListNode_CreateWithAllocator(dict->mRefAllocator);
            RefDictListNode_Append(dict->mNodeTable[index], old_primtive_node);
            RefDictListNode_Append(dict->mNodeTable[index], primtive_node);
            RefObject_DecRef(primtive_node);
            RefObject_DecRef(old_primtive_node);
        } else if (RefDictListNode_IsValid(dict->mNodeTable[index])) {
            /*printf("RefDict_SetItem(): append ListNode\n");*/
            RefDictListNode_Append(dict->mNodeTable[index], primtive_node);
            RefObject_DecRef(primtive_node);
        } else {
            assert(!"NOT_REACHED");
        }
    } else {
        dict->mNodeTable[index] = primtive_node;
    }
    dict->mNumNode += 1;
    return 0;
}

int
RefDict_SetItemCString(RefObject *aRefDict, unsigned char *aKeyCString, int aLength, 
                       RefObject *aRefValue)
{
    RefDict *dict;
    RefObject *refstring;
    int result;
    dict = RefObject_GetObject(aRefDict);
    refstring = RefString_CreateDuplicateWithAllocator(aKeyCString, aLength, dict->mRefAllocator);
    result = RefDict_SetItem(aRefDict, refstring, aRefValue);
    RefObject_DecRef(refstring);
    return result;
}

RefObject *
RefDict_GetItem(RefObject *aRefDict, RefObject *aRefKeyString)
{
    RefDict *dict;
    RefObject *node;
    unsigned char *key_cstring;
    int key_cstring_len;
    unsigned long full_hash;
    int index;
    dict = RefObject_GetObject(aRefDict);
    key_cstring = RefString_AsString(aRefKeyString);
    key_cstring_len = RefString_GetLength(aRefKeyString);
    full_hash = RefDict_HashWithLength(key_cstring, key_cstring_len);
    index = full_hash & (dict->mNodeTableSize - 1);
    node = dict->mNodeTable[index];
    if (!node) {
        return NULL;
    }
    if (RefDictPrimitiveNode_IsValid(node)) {
        RefDictPrimitiveNode *primitive_node;
        primitive_node = RefObject_GetObject(node);
        if (full_hash == primitive_node->mHash &&
            RefString_CompareRefString(primitive_node->mRefKeyString, aRefKeyString) == 0) {
            return primitive_node->mRefValue;
        } else {
            /* not found */
            return NULL;
        }
    } else if (RefDictListNode_IsValid(node)) {
        return RefDictListNode_GetItem(node, full_hash, key_cstring, key_cstring_len);
    } else {
        assert(!"NOT_REACHED");
        return NULL;
    }
}

RefObject *
RefDict_GetItemCString(RefObject *aRefDict, unsigned char *aKeyCString, int aLength)
{
    RefDict *dict;
    RefObject *refstring;
    RefObject *refvalue;
    dict = RefObject_GetObject(aRefDict);
    refstring = RefString_CreateShallowWithAllocator(aKeyCString, aLength, dict->mRefAllocator);
    refvalue = RefDict_GetItem(aRefDict, refstring);
    RefObject_DecRef(refstring);
    return refvalue;
}

RefObject *
RefDict_TakeOutItem(RefObject *aRefDict, RefObject *aRefKeyString)
{
    RefDict *dict;
    RefObject *node;
    unsigned char *key_cstring;
    int key_cstring_len;
    unsigned long full_hash;
    int index;
    dict = RefObject_GetObject(aRefDict);
    key_cstring = RefString_AsString(aRefKeyString);
    key_cstring_len = RefString_GetLength(aRefKeyString);
    full_hash = RefDict_HashWithLength(key_cstring, key_cstring_len);
    index = full_hash & (dict->mNodeTableSize - 1);
    node = dict->mNodeTable[index];
    if (!node) {
        return NULL;
    }
    if (RefDictPrimitiveNode_IsValid(node)) {
        RefDictPrimitiveNode *primitive_node;
        primitive_node = RefObject_GetObject(node);
        if (full_hash == primitive_node->mHash &&
            RefString_CompareRefString(primitive_node->mRefKeyString, aRefKeyString) == 0) {
            RefObject *refobj;
            refobj = primitive_node->mRefValue;
            RefObject_IncRef(refobj);
            RefObject_DecRef(node);
            dict->mNodeTable[index] = NULL;
            dict->mNumNode -= 1;
            return refobj;
        } else {
            return NULL;
        }
    } else if (RefDictListNode_IsValid(node)) {
        RefObject *refobj;
        refobj = RefDictListNode_TakeOutItem(node, full_hash, key_cstring, key_cstring_len);
        if (!refobj) {
            return NULL;
        }
        if (RefDictListNode_GetSize(node) == 1) {
            RefObject *primitive_node;
            primitive_node = RefDictListNode_GetItemByIndex(node, 0);
            assert(primitive_node);
            assert(RefDictPrimitiveNode_IsValid(primitive_node));
            RefObject_IncRef(primitive_node);
            RefObject_DecRef(node);
            dict->mNodeTable[index] = primitive_node;
        }
        dict->mNumNode -= 1;
        return refobj;
    } else {
        assert(!"NOT_REACHED");
        return NULL;
    }
}

RefObject *
RefDict_TakeOutItemCString(RefObject *aRefDict, unsigned char *aKeyCString, int aLength)
{
    RefDict *dict;
    RefObject *refstring;
    RefObject *refvalue;
    dict = RefObject_GetObject(aRefDict);
    refstring = RefString_CreateShallowWithAllocator(aKeyCString, aLength, dict->mRefAllocator);
    refvalue = RefDict_TakeOutItem(aRefDict, refstring);
    RefObject_DecRef(refstring);
    return refvalue;
}

int
RefDict_DeleteItem(RefObject *aRefDict, RefObject *aRefKeyString)
{
    RefObject *refobj;
    refobj = RefDict_TakeOutItem(aRefDict, aRefKeyString);
    if (refobj) {
        RefObject_DecRef(refobj);
        return 1;
    } else {
        return 0;
    }
}

int
RefDict_DeleteItemCString(RefObject *aRefDict, unsigned char *aKeyCString, int aLength)
{
    RefDict *dict;
    RefObject *refstring;
    int result;
    dict = RefObject_GetObject(aRefDict);
    refstring = RefString_CreateShallowWithAllocator(aKeyCString, aLength, dict->mRefAllocator);
    result = RefDict_DeleteItem(aRefDict, refstring);
    RefObject_DecRef(refstring);
    return result;
}

int
RefDict_Contains(RefObject *aRefDict, RefObject *aRefKeyString)
{
    return (RefDict_GetItem(aRefDict, aRefKeyString) != NULL);
}

int
RefDict_ContainsCString(RefObject *aRefDict, unsigned char *aKeyCString, int aLength)
{
    /* TODO */
    return 0;
}

int
RefDict_GetSize(RefObject *aRefDict)
{
    return ((RefDict *)RefObject_GetObject(aRefDict))->mNumNode;
}
